package com.nanbei.sort;

import java.util.Arrays;

/**
 * @ClassDescription: 快速排序 (单边快排)
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/6/26 17:02
 */
public class QuickSortLomuto {
    public static void main(String[] args) {
        int[] ints = {6,1,11,32, 4, 3,5,6,7};
        int[] bubbling = selection(ints);
        System.out.println(Arrays.toString(bubbling));
    }

    public static int[] selection(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = querySort(nums, left, right);
        sort(nums, left, i - 1);
        sort(nums, i + 1, right);
    }

    /**
     * - 选择最右侧元素作为基准点
     * - min 找比基准点小的，max 找比基准点大的，一旦找到，二者进行交换
     * - 交换时机：min 找到小的，且与 max 不相等
     * - max 找到 >= 基准点元素后，不应自增
     * - 最后基准点与 max 交换，max 即为基准点最终索引
     *
     * @param nums  数组
     * @param left  左边界
     * @param right 右边界
     * @return 基点下标
     */
    private static int querySort(int[] nums, int left, int right) {
        int max = left, min = left;
        int pv = nums[right];
        while (min < right) {
            if (nums[min] < pv) {
                if (max != min) {
                    swap(nums, max, min);
                }
                max++;
            }
            min++;
        }

        swap(nums, right, max);
        return max;

    }

    public static void swap(int[] nums, int i, int j) {
        Sort.swap(nums, i, j);
    }



}
